package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-25 16:46
 */
public class exist79 {

    /**79. 单词搜索
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     * 回溯：遍历数组，以数组中每个元素为起点进行回溯判断
     * 路径：已经遍历到的元素
     * 选择列表：上下左右中没有被访问过的元素
     * 终止条件：没有匹配上，或周围元素都被访问过
     * */

    boolean backtrack(char[][] board,String word,int i,int j,int index){
        if (index==word.length()) return true;
        if (i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!=word.charAt(index)) return false;
        char cur=board[i][j];
        board[i][j]='#';
        boolean res=backtrack(board,word,i-1,j,index+1)||backtrack(board,word,i+1,j,index+1)||
                backtrack(board,word,i,j-1,index+1)||backtrack(board,word,i,j+1,index+1);
        board[i][j]=cur;
        return res;
    }
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backtrack(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
}
